#include "KMP.hpp"


/**
 * @brief Construct a new kmp matcher::kmp matcher object
 * 
 * @param T 被模式串匹配的串
 * @param P 模式串
 */
KMP_Matcher::KMP_Matcher(string T, string P){
    this->T = "x" + T;
    this->P = "x" + P;
    this->T_length = T.length();
    this->P_length = P.length();
}


/**
 * @brief 计算pi函数
 * 
 * @return vector<int> pi数组
 * 
 * @note 从类的私有属性中去的仓库
 */
vector<int> KMP_Matcher::compute_prefix_function(){
    int m = this->P_length;
    vector<int> pi = vector<int>(m+1);
    pi[1] = 0;
    int k = 0;
    for (size_t q = 2; q <= m; q++)
    {
        while (k > 0 and this->P[k+1] != P[q])
        {
            k = pi[k];
        }
        if (P[k+1] == P[q])
        {
            k = k + 1;
        }
        pi[q] = k;
    }
    return pi;
}


/**
 * @brief 运行KMP匹配算法
 * 
 */
void KMP_Matcher::run_KMP_Matcher(){
    auto n = this->T_length;
    auto m = this->P_length;
    this->pi = this->compute_prefix_function();
    int q = 0;
    for (size_t i = 1; i <= n; i++)
    {
        while (q>0 and this->P[q+1] != T[i])
        {
            q = pi[q];
        }
        if(P[q + 1] == T[i]){
            q = q + 1;
        }
        if (q == m)
        {
            cout << "Pattern occurs with shift " << i - m << endl;
            q = pi[q];
        }
    }
}


/**
 * @brief 打印pi数组。要先运行compute_prefix_function
 * 
 */
void KMP_Matcher::print_pi(){
    if (pi.size() != this->P_length+1)
    {
        cout << "please run run_KMP_Matcher()" << endl;
        return;
    }
    cout << "pi = ";
    for (size_t i = 0; i < pi.size(); i++)
    {
        cout << pi[i];
        if (i < pi.size() - 1)
        {
            cout << ", ";
        }
        
    }
    cout << endl;
    
}